package lc.dfs;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 电话号码的字母组合
 *
 * @author yang
 * @date 2022/1/16
 */
public class 电话号码的字母组合 {
    List<String> res = new ArrayList<>();
    public List<String> letterCombinations(String digits) {

        String[] strs = {
                "","","abc","def",
                "ghi","jkl","mno",
                "pqrs","tuv","wxyz"
        };
        if (digits.length() == 0) return new ArrayList<>();

        dfs(digits,strs,0,"");
        return res;
    }

    private void dfs(String digits, String[] strs, int u, String path) {
        int n = digits.length();
        if (n == u) {
            res.add(path);
            return;
        }
        String s =  strs[digits.charAt(u) - '0'];
        for (int i = 0; i < s.length(); i++) {
            String cur = path;
            path += s.charAt(i);
            dfs(digits,strs,u+1,path);
            path = cur;
        }

    }
}
